package com.leetcode.search.bfs;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

/**
 * @author Dennis Li
 * @date 2020/7/25 19:39
 */
public class LadderLength_127 {

    public int ladderLength(String beginWord, String endWord, List<String> wordList) {
        wordList.add(beginWord);
        final int N = wordList.size();
        int start = N - 1;
        int end = 0;
        while (end < N && !wordList.get(end).equals(endWord))
            end++;
        // 不存在这样的序列
        if (end == N) return 0;
        final List<Integer>[] graph = buildGraph(wordList);
        return getShortestPath(start, end, graph);
    }

    private List<Integer>[] buildGraph(List<String> wordList) {
        final int len = wordList.size();
        List<Integer>[] graph = new List[len];
        for (int i = 0; i < len; i++) {
            graph[i] = new ArrayList<>();
            for (int j = 0; j < len; j++) {
                if (isConnect(wordList.get(i), wordList.get(j)))
                    graph[i].add(j);
            }
        }
        return graph;
    }

    private boolean isConnect(String s1, String s2) {
        final int length = s1.length();
        int diff = 0;
        for (int i = 0; i < length && diff <= 1; i++) {
            if (s1.charAt(i) != s2.charAt(i))
                diff++;
        }
        return diff == 1;
    }

    private int getShortestPath(int start, int end, List<Integer>[] graph) {
        final Queue<Integer> queue = new LinkedList<>();
        final boolean[] marked = new boolean[start + 1];
        marked[start] = true;
        queue.offer(start);
        int path = 1;
        while (!queue.isEmpty()) {
            int size = queue.size();
            path++;
            while (size-- > 0) {
                final int now = queue.poll();
                for (int node : graph[now]) {
                    if (node == end)
                        return path;
                    if (marked[node])
                        continue;
                    marked[node] = true;
                    queue.offer(node);
                }
            }
        }
        return 0;
    }

}
